package com.lsa.letcode.the142.linkedListCycleII;

import com.lsa.letcode.common.ListNode;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode n) {
    	ListNode slow = n;
    	if (slow == null){
    		return null;
    	}
    	ListNode fast = slow.next;
    	
    	// if we get to null at some point, it will be fast pointer ->
    	// no check for slow
    	while(fast != null){
    		slow = slow.next;
    		fast = fast.next;
    		if (fast != null){
    			fast = fast.next;
    		}
    		if (slow == fast) {
    			break;
    		}
    	}
    	
    	if (fast == null){
    		return null;
    	}
    	
    	slow = slow.next;
    	while(n != slow){
    		slow = slow.next;
    		n = n.next;
    	}
    	
    	return n; 
    }
}